package com.example;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 判断数组中所有的数字是否只出现一次。给定一个数组array，判断数组 array 中是否所有的数字都只 出现过一次。
 * 例如，arr = {1, 2, 3}，输出 YES。又如，arr = {1, 2, 1}，输出 NO。约束时间复杂度为 O(n)。
 */
public class ArrayNoRepeat {
    /**
     * 计算有序的数组.
     * @param array
     * @return
     */
    public static String calFromQueue(int[] array){
        int sameNum = array[0];
        for (int i = 1; i < array.length; i++) {
            /* 在有序数组中,若后一个的元素与前一个元素相同,则数组中的数字不是唯一,即"NO" */
            if(sameNum == array[i]){
                return "NO";
            }
            sameNum = array[i];
        }
        return "YES";
    }

    /**
     * 计算无序的数组
     * @param array
     * @return
     */
    public static String calFromNoQueue(int[] array){
        Set<Integer> sameSet = new HashSet<>();
        for (int i = 0; i < array.length; i++) {
            /* 若集合包含,则有重复的数字,则数组中的数字不是唯一,即"NO" */
            if(sameSet.contains(array[i])){
                return "NO";
            }
            /*添加进入唯一数组set集合中*/
            sameSet.add(array[i]);
        }
        return "YES";
    }

    public static void main(String[] args ){
        int[] arrayNoRepeat = {1,2,3};
        int[] arrayRepeat = {1,2,3,4,5,5,6};
        int[] arrayRandomRepeat = {1,6,8,5,10,11,12,7,10};
        int[] arrayRandomNoRepeat = {1,6,8,5,11,12,7,10};

        String commonWord = " 数组中是否所有的数字都只出现过一次? ";

        System.out.println(Arrays.toString(arrayNoRepeat) + commonWord + calFromQueue(arrayNoRepeat));

        System.out.println(Arrays.toString(arrayRepeat) + commonWord + calFromQueue(arrayRepeat));

        System.out.println(Arrays.toString(arrayRandomRepeat) + commonWord + calFromNoQueue(arrayRandomRepeat));

        System.out.println(Arrays.toString(arrayRandomNoRepeat) + commonWord + calFromNoQueue(arrayRandomNoRepeat));
    }
}
